﻿// 1002 棋盘覆盖问题.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <memory.h>

using namespace std;
/*
http://oj.daimayuan.top/course/14/problem/798

现在有一个 n行 n列的棋盘，坐标范围从 (1,1)−(n,n)
，你需要用 1×2的多米诺骨牌去覆盖这张棋盘。

这张棋盘上有 m个格子已经放置了棋子，即这些格子不能被覆盖，现在要你求出骨牌最多可以覆盖多少个格子。

第一行输入 n,m。

接下来 m行，每行两个数字 xi,yi表示棋子的坐标。

输出一个数表示最多覆盖的格子数。

输入格式
第一行两个整数 n,m。

接下来 m行，每行有两个整数。

输出格式
输出一个数字表示答案。

样例输入
3 1
2 2
样例输出
8
数据规模
对于所有数据，保证 2≤n≤40,0≤m≤n2,1≤xi,yi≤n,棋子所在格子各不相同。
*/
vector<int> edge[801];
int D[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int n, m, a[41][41], n1, n2, r[41][41], v[801];
bool b[801];

int find(int x) {
	b[x] = true;
	for(auto y:edge[x])
		if (!v[y] || (!b[v[y]] && find(v[y]))) {
			v[y] = x;
			return true;
		}
	return false;
}


int match() {
	int ans = 0;
	memset(v, 0, sizeof v);
	for (int i = 1; i <= n1; i++) {
		memset(b, false, sizeof b);
		if (find(i))
			++ans;
	}
	return ans;

}

int main()
{
	scanf("%d%d",&n,&m);
	memset(a,0,sizeof a);
	n1 = n2 = 0;
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d",&x,&y);
		a[x][y] = 1;
	}

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (!a[i][j])
				if ((i + j) & 1)
					r[i][j] = ++n2;
				else
					r[i][j] = ++n1;

	for(int i= 1;i<=n;i++)
		for(int j= 1;j<=n;j++)
			if(!a[i][j] && !((i+j)&1))
				for (int k = 0; k < 4; k++) {
					int x = i + D[k][0]; int y = j + D[k][1];
					if (x<1 || x>n || y<1 || y>n || a[x][y])
						continue;
					edge[r[i][j]].push_back(r[x][y]);
				}

	printf("%d\n", 2 * match());

	return 0;
}

 